package tree;


/**
 *  https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
 */

public class RBTree<T extends Comparable <T>> {
    private RBNode<T> mRoot;

    private static final boolean RED = false;
    private static final boolean BLACK = true;

    public class RBNode<T extends Comparable <T>>{
        boolean color;
        T key;
        RBNode<T> left;
        RBNode<T> right;
        RBNode<T> parent;
        public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {
            this.key = key;
            this.color = color;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * /*
     *  * 对红黑树的节点(x)进行左旋转
     *  *
     *  * 左旋示意图(对节点x进行左旋)：
     *  *       px                               px
     *  *      /                                /
     *  *    x                               y
     *  *  /  \      --(左旋)-.            /   \                #
     *  *lx    y                         x     ry
     *  *     /  \                     /  \
     *  *   ly    ry                   lx  ly
     *  *
     *  *
     *  *
     * @param x hg
     */
    private void leftRotate(RBNode<T> x){
        RBNode<T> y = x.right;

        x.right = y.left;
        if(y.left !=null){
            y.left.parent = x;
        }

        y.parent = x.parent;
        if(x.parent == null){
            this.mRoot = y;
        }else {
            if(x.parent.left == x){
                x.parent.left = y;
            }else {
                x.parent.right = y;
            }
        }

        y.left = x;
        x.parent = y;


    }


    /**
     * /*
     *  * 对红黑树的节点(y)进行右旋转
     *  *
     *  * 右旋示意图(对节点y进行左旋)：
     *  *              py                               py
     *  *            /                                /
     *  *          y                                x
     *  *        /  \      --(右旋)-.              /  \                     #
     *  *       x   ry                           lx   y
     *  *      / \                                   / \                   #
     *  *     lx  rx                                rx  ry
     *  *
     *  *
     * @param y
     */
    private void rightRotate(RBNode<T> y){
        RBNode<T> x = y.left;

        y.left = x.right;
        if(x.right !=null){
            x.right.parent = y;
        }

        x.parent = y.parent;
        if(y.parent == null){
            this.mRoot = x;
        }else {
            if(y.parent.left == y){
                y.parent.left = x;
            }else {
                y.parent.right = x;
            }
        }

        x.right = y;
        y.parent =x;
    }

    /**
     *
     * @param node
     */
    private void insert(RBNode<T> node) {
        int cmp;
        RBNode<T> y = null;
        RBNode<T> x = this.mRoot;

        // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
        while (x != null) {
            y = x;
            cmp = node.key.compareTo(x.key);
            if (cmp < 0)
            {
                x = x.left;
            }
            else
            {
                x = x.right;
            }
        }

        node.parent = y;
        if (y!=null) {
            cmp = node.key.compareTo(y.key);
            if (cmp < 0)
            {
                y.left = node;
            }
            else
            {
                y.right = node;
            }
        } else {
            this.mRoot = node;
        }

        // 2. 设置节点的颜色为红色
        node.color = RED;

        // 3. 将它重新修正为一颗二叉查找树
//        insertFixUp(node);
    }

    /**
     *
     * @param key
     */
    public void insert(T key) {
        insert(new RBNode<>(key,BLACK,null,null,null));
    }
}
